#include <bits/stdc++.h>
#pragma	GCC optimize(3)

//#define	Debug

using namespace std;

const int	INF=0x7f7f7f7f;
const int	NA=-INF;

template<const int _n,const int _m>
struct Edge
{
	struct Edge_base { int	to,next; } e[_m]; int	cnt,p[_n];
	Edge() { clear(); } void clear() { cnt=0,memset(p,0,sizeof(p)); }
	void	insert(const int x,const int y)
	{ e[++cnt].to=y; e[cnt].next=p[x]; p[x]=cnt; return ; }
	int	start(const int x) { return p[x]; }
	Edge_base&	operator[](const int x) { return e[x]; }
};

int	n,m;

struct LCT
{
	struct F
	{
		int	a,b,c,d; F() {}
		F(const int _a,const int _b,const int _c,const int _d)
			:a(_a),b(_b),c(_c),d(_d) {}
		void	Merge_info(const int x,const int y)
		{
			if(x>a)c=a,d=b,a=x,b=y;
			else if(x==a)b+=y;
			else if(x>c)c=x,d=y;
			else if(x==c)d+=y;
		}
	};

	struct node
	{
		int	val,size,Max1,Max2,addf,chgf,revf,Cnt1,Cnt2;
		node	*s[2],*fa; node() { }
		node(const int x) { val=Max1=x,Max2=chgf=NA,addf=revf=0;
			size=Cnt1=1,Cnt2=0; s[0]=s[1]=fa=0; }

		node *	link(const int w,node * t)
		{ if((s[w]=t))t->fa=this; return this; }

		void	update()
		{
			F	a(NA,0,NA,0); a.Merge_info(val,1);
			if(s[0])a.Merge_info(s[0]->Max1,s[0]->Cnt1);
			if(s[0])a.Merge_info(s[0]->Max2,s[0]->Cnt2);
			if(s[1])a.Merge_info(s[1]->Max1,s[1]->Cnt1);
			if(s[1])a.Merge_info(s[1]->Max2,s[1]->Cnt2);
			Max1=a.a,Cnt1=a.b,Max2=a.c,Cnt2=a.d;
			size=(s[0]?s[0]->size:0)+(s[1]?s[1]->size:0)+1;
			return ;
		}

		void	pd() { if(s[0])s[0]->push_down();
			if(s[1])s[1]->push_down(); return ; }
		void	push_down()
		{
			if(chgf!=NA)
			{ val=Max1=chgf; Max2=NA; Cnt1=size; Cnt2=0;
				if(s[0])s[0]->chgf=chgf,s[0]->addf=0;
				if(s[1])s[1]->chgf=chgf,s[1]->addf=0; chgf=NA; }
			if(addf)
			{
				val+=addf;
				Max1+=addf;
				if(Max2!=NA)Max2+=addf;
				if(s[0])s[0]->addf+=addf;
				if(s[1])s[1]->addf+=addf;
				addf=0;
			}
			if(revf)
			{
				swap(s[0],s[1]);
				if(s[0])s[0]->revf^=1;
				if(s[1])s[1]->revf^=1;
				revf=0;
			}
		}

		node * access()
		{
			for(node * p=this,* q=0; p; q=p,p=p->fa)
			{
				p->splay()->link(1,q);
				p->update();
			}
			return splay();
		}

		void	add(const int x)
		{
			addf+=x;
			push_down();
			return ;
		}
		void	reverse()
		{
			revf^=1;
			push_down();
			return ;
		}
		void	change(const int x)
		{
			chgf=x;
			addf=0;
			push_down();
			return ;
		}
		void	access_change(const int w)
		{
			for(node *p=this,*q=0; p; q=p,p=p->fa)
			{
				p->splay();
				if(!p->fa)
				{
					if(p->s[1])p->s[1]->change(w);
					if(q)q->change(w);
					p->val=w;
					p->update();
					return ;
				}
				p->link(1,q),p->update();
			}
			return ;
		}

		void	access_add(const int w)
		{
			for(node *p=this,*q=0; p; q=p,p=p->fa)
			{
				p->splay();
				if(!p->fa)
				{
					if(p->s[1])p->s[1]->add(w);
					if(q)q->add(w);
					p->val+=w;
					p->update();
					return ;
				}
				p->link(1,q);
				p->update();
			}
			return ;
		}

		pair<int,int>	access_query()
		{
			for(node *p=this,*q=0; p; q=p,p=p->fa)
			{
				p->splay();
				if(!p->fa)
				{
					F	a(NA,0,NA,0);
					a.Merge_info(p->val,1);
					if(p->s[1])a.Merge_info(p->s[1]->Max1,p->s[1]->Cnt1);
					if(p->s[1])a.Merge_info(p->s[1]->Max2,p->s[1]->Cnt2);
					if(q)a.Merge_info(q->Max1,q->Cnt1);
					if(q)a.Merge_info(q->Max2,q->Cnt2);
					Max1=a.a,Cnt1=a.b,Max2=a.c,Cnt2=a.d;
					return make_pair(Max2,Cnt2);
				}
				p->link(1,q);
				p->update();
			}
			return make_pair(NA,0);
		}

		bool	isroot()
		{
			return !fa || (fa->s[0]!=this && fa->s[1]!=this);
		}
		bool	getlr()
		{
			return fa->s[1]==this;
		}
		void	pdfr()
		{
			if(!isroot())fa->pdfr();
			pd();
		}
		node * splay()
		{
			pdfr();
			while(!isroot() && !fa->isroot())
				(getlr()==fa->getlr()?fa->rot():rot()),rot();
			if(!isroot())rot();
			update();
			return this;
		}

		node * rot()
		{
			node *gfa=fa->fa;
			bool fl=fa->isroot();
			getlr()?link(0,fa->link(1,s[0])):link(1,fa->link(0,s[1]));
			fa->update();
			if(!fl)gfa->link(gfa->s[1]==fa,this);
			else	fa=gfa;
			return this;
		}
	} U[110000],*P[110000];

	LCT()
	{
		memset(U,0,sizeof(U));
		memset(P,0,sizeof(P));
	}

	template<const int _n,const int _m>
	void	build(Edge<_n,_m> e,const int * a,const int N)
	{
		int	i,t;
		queue<int>Q;
		for(i=0; i<N; ++i)P[i+1]=new(U+i+1)node(a[i+1]);
		Q.push(1);
		while(!Q.empty())
		{
			t=Q.front();
			Q.pop();
			for(i=e.start(t); i; i=e[i].next)
			{
				if(e[i].to!=P[t]->fa-U)
				{
					P[e[i].to]->fa=P[t];
					Q.push(e[i].to);
				}
			}
		}
		return ;
	}

	node * find_root(node * t)
	{
		node * s;
		for(s=t->access(); s->pd(),s->s[0]; s=s->s[0]);
		return s;
	}
	node *	get_root(node * t)
	{
		while(t && !t->isroot())t=t->fa;
		return t;
	}
	void	change_root(node * t)
	{
		t->access();
		t->reverse();
		return ;
	}
	void	cut(node * t)
	{
		t->access();
		t->s[0]->fa=0;
		t->s[0]=0;
		t->update();
	}
	void	cut(node * t,node * s)
	{
		if(t==s || find_root(t)!=find_root(s))return ;
		change_root(s);
		cut(t);
	}
	void	link(node *t,node *s)
	{
		if(find_root(t)==find_root(s))return ;
		change_root(t);
		t->fa=s;
	}
	void	cut(const int x,const int y)
	{
		cut(P[x],P[y]);
		return ;
	}
	void	link(const int x,const int y)
	{
		link(P[x],P[y]);
		return ;
	}
	void	change(node * t,node *s,const int w)
	{
		t->access();
		s->access_change(w);
		return ;
	}
	void	add(node * t,node *s,const int w)
	{
		t->access();
		s->access_add(w);
		return ;
	}
	void	change(const int x,const int y,const int z)
	{
		change(P[x],P[y],z);
		return ;
	}
	void	add(const int x,const int y,const int z)
	{
		add(P[x],P[y],z);
		return ;
	}
	pair<int,int>	query(node * t,node * s)
	{
		t->access();
		return s->access_query();
	}
	pair<int,int>	query(const int x,const int y)
	{
		return query(P[x],P[y]);
	}

#ifdef	Debug
	void	Pr(node * t)
	{
		if(t->s[0])printf("(%2d:%11d)%5ld===L==>%5ld(%2d:%11d)\n",
					  t->Max1,t->Max2,t-U,t->s[0]-U,t->s[0]->Max1,t->s[0]->Max2),Pr(t->s[0]);
		if(t->s[1])printf("(%2d:%11d)%5ld===R==>%5ld(%2d:%11d)\n",
					  t->Max1,t->Max2,t-U,t->s[1]-U,t->s[1]->Max1,t->s[1]->Max2),Pr(t->s[1]);
		return ;
	}

	void	Pr_tree()
	{
		printf("=====================================\n");
		for(int i=1; i<=n; ++i)
		{
			if(P[i]->isroot() && P[i]->fa)
			{
				printf("(%2d:%11d)%5ld---N-->%5ld(%2d:%11d)\n",P[i]->fa->Max1,P[i]->fa->Max2,
				       P[i]->fa-U,P[i]-U,P[i]->Max1,P[i]->Max2), Pr(get_root(P[i]));
			}
			if(P[i]->isroot() && !P[i]->fa) Pr(get_root(P[i]));
		}
		return ;
	}
#endif
} S;

int	a[110000];
Edge<110000,210000>e;

int main()
{
	int	T,i,x,y,z,zz;
	scanf("%d",&T);
	for(int K=1; K<=T; ++K)
	{
		e.clear();
		printf("Case #%d:\n",K);
		scanf("%d%d",&n,&m);
		for(i=1; i<=n; ++i) scanf("%d",&a[i]);
		for(i=1; i<n; ++i) scanf("%d%d",&x,&y), e.insert(x,y),e.insert(y,x);
		S.build(e,a,n);
#ifdef	Debug
		S.Pr_tree();
#endif
		while(m--)
		{
			int	op;
			scanf("%d",&op);
			if(op==1)//Change an Edge
			{
				scanf("%d%d%d%d",&x,&y,&z,&zz);
				S.cut(x,y);
				S.link(z,zz);
			}
			if(op==2)//Make value on path the same
			{
				scanf("%d%d%d",&x,&y,&z);
				S.change(x,y,z);
			}
			if(op==3)//Add a number to value on the path
			{
				scanf("%d%d%d",&x,&y,&z);
				S.add(x,y,z);
			}
			if(op==4)//Query second Max val
			{
				scanf("%d%d",&x,&y);
				pair<int,int>	temp=S.query(x,y);
				if(temp.first==NA)printf("ALL SAME\n");
				else	printf("%d %d\n",temp.first,temp.second);
			}
		}
	}
	return 0;
}
